package priorityQueue;

import java.util.Arrays;
import java.util.Comparator;

public class PriorityQueue {


    public int[] elem;
    public int usedSize;

    public PriorityQueue() {
        this.elem = new int[10];
    }

    public void initHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
        //初始化了elem 方便实现接口
    }

    public void createHeap() {
        for (int p = (usedSize-2) / 2; p >= 0; p--) {
            shiftDown(p, usedSize);
        }
    }

    private void shiftDown(int root,int len) {
        //root为父节点    child为左右节点中大的那个
        int child = root * 2 + 1;
        while (child < usedSize) {
            if(child+1 < len && elem[child] < elem[child+1]) {
                child = child + 1;
            }
            if(elem[child] > elem[root]) {
                swap(elem[child], elem[root]);
                root = child;
                child = root*2 + 1;
            }else {
                break;
            }
        }
    }

    private void shiftUp(int child) {
        int p = (child-1) / 2;
        while (child > 0) {
            if (elem[child] > elem[p]) {
                swap(child, p);
                child = p;
                p = (child-1) / 2;
            } else {
                break;
            }
        }
    }

    private void swap(int a, int b) {
        int tmp = elem[a];
        elem[a] = elem[b];
        elem[b] = elem[a];
    }

    public void push(int val) {
        if(isFall()) {
            this.elem = Arrays.copyOf(elem, 2 * elem.length);
        }
        this.elem[usedSize] = val;
        //向上调整
        shiftUp(usedSize);

        usedSize++;
    }

    public boolean isFull() {
        return usedSize == elem.length;
    }

    public int pollHeap() {
        int ret = elem[0];
        swap(elem[0], elem[usedSize-1]);
        usedSize--;
        shiftDown(0, usedSize);
        
        return ret;
    }

    public boolean isFall() {
        return !(elem.length == usedSize);
    }

    public int peekHeap() {
        return elem[0];
    }
    // 最小K个数1
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];

        if(arr == null || k <= 0) {
            return ret;
        }

        java.util.PriorityQueue<Integer> priorityQueue =
                new java.util.PriorityQueue<>(arr.length);

        for (int i = 0; i < arr.length; i++) {
            priorityQueue.offer(arr[i]);
        }

        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }

        return ret;
    }

    // 最小K个数2
    class IntCmp implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    }
    public int[] smallestK2(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null || k <= 0) {
            return ret;
        }
        java.util.PriorityQueue<Integer> priorityQueue =
                new java.util.PriorityQueue<>(new IntCmp());

        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }

        for (int i = k; i < arr.length; i++) {
            if(arr[i] < priorityQueue.peek()) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }

        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }

        return ret;
    }

    // 最大K个数
    public int[] smallestK3(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null || k <= 0) {
            return ret;
        }
        java.util.PriorityQueue<Integer> priorityQueue = new java.util.PriorityQueue<>(k);

        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }

        for (int i = k; i < arr.length; i++) {
            if(arr[i] > priorityQueue.peek()) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }

        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }

        return ret;
    }
}
